/*
 * File:       eg_geom.c
 * Created on: Aug 26, 2009
 * Purpose:    Contains functions dealing with geometry
 */

/*
 Copyright 2009 James Youngquist, Colin Scott.

 This file is part of ElectroGladiator.  ElectroGladiator is free
 software: you can redistribute it and/or modify it under the terms
 of the GNU General Public License as published by  the Free
 Software Foundation, either version 3 of the License, or (at your
 option) any later version.

 You should have received a copy of the GNU General Public License
 along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <math.h>

#include "eg_geom.h"

/**
 * looks for intersection
 * Returns 1 if an intersection is found and sets p to that point if non NULL
 * Returns 0 if no intersection found.
 */
int intersection(const Line *l1, const Line *l2, Point *p) {
    double x = -1.0; // game map is in first quadrant
    double y = -1.0;

    // lines aren't both vertical
    if (!is_vertical(l1) && !is_vertical(l2)) {
        // compute slopes
        double m1 = slope(l1);
        double m2 = slope(l2);

        // parallel lines considered to have no intersection
        if (fnear(m1, m2)) {
            return 0;
        } else {
            x = (-m2 * l2->p1.x + l2->p1.y + m1 * l1->p1.x - l1->p1.y) / (m1
                    - m2);
            y = m1 * (x - l1->p1.x) + l1->p1.y;
        }
    }

    // l1 not vertical
    else
        if (!is_vertical(l1)) {
            double m1 = slope(l1);
            x = l2->p1.x; // could be l2->p2.x just as easily
            y = m1 * (x - l1->p1.x) + l1->p1.y;
        }

        // l2 not vertical
        else {
            double m2 = slope(l2);
            x = l1->p1.x;
            y = m2 * (x - l2->p1.x) + l2->p1.y;
        }

    // test intersection occurs where lines exist.  Assumes that no line will
    // exist outside the map's boundaries
    Point tmp = { x, y };
    if (inside_bb(l1, &tmp) && inside_bb(l2, &tmp)) {
        if (p) {
            p->x = x;
            p->y = y;
        }
        return 1;
    } else {
        // here the original contents of *p are unchanged
        return 0;
    }
}

/**
 * Finds all intersections along line l and adds them to inters as new points
 * allocated in memory.
 * Returns Point closest to a player from a list of Points.  This clears the
 * list.
 */
void find_intersections(Map *map, Line *l, LL *inters) {
    int i; // Generic index.
    Point inter; // an intersection

    for (i = 0; i < map->num_lines; i++) {
        if (intersection(l, map->lines[i], &inter)) {
            ll_push(inters, new_point(inter.x, inter.y));
        }
    }

    // Removing duplicate points from the list
    remove_duplicate_pts(inters);

    return;
}

Point* closest_point(Player *p, LL *inters) {
    Point *closest_p; // Closest intersection to player.
    Point *tmp_p; // Temporary point
    
    closest_p = (Point*) ll_pop(inters);
    while ((tmp_p = (Point*) ll_pop(inters))) {
        double old_dist = distance(&(Point) {
                    p->location.x - closest_p->x,
                    p->location.y - closest_p->y
                }
                );
                double new_dist = distance(&(Point) {
                            p->location.x - tmp_p->x,
                            p->location.y - tmp_p->y
                        }
                );

                if (new_dist < old_dist) { // if closer use the new value
                    free_point(closest_p);
                    closest_p = tmp_p;
                } else { // otherwise throw it out
                    free_point(tmp_p);
                }
            }

            return closest_p;
        }

        // Returns the Line in a Map that contains the given Point. Ugly hax right
        // now; need a more elegant way than checking intersections with a line all
        // over again to make this function more generic.  Good thing to check
        // mathematically, but I don't know accuracy of floating point numbers like
        // that. Another problem is to return the correct line when 2+ lines all
        // satisfy the intersection test, e.g. where several lines share the same
        // end point, but not all of them may be in the FOV.
Line* line_with_point(Map *map, Point *p, Line *FR_l, Line *FL_l, Player *pl) {
    int i; // Generic index.
    Point inter; // Just some intersection.
    Line *match = NULL; // The matching line, there might not be one

    // Anyway, consider each line on the map and if it
    //  1: results in an intersection with the passed in line
    //  2: has the same intersection as the passed in point
    //  3: that line contains more than one point within FOV (between l1 & l2)
    //     where this is tested by an intersection with l2 or an endpoint
    //     within the FOV that is not the intersection.
    // then it is our match.
    for (i = 0; i < map->num_lines; i++) {
        if (intersection(FR_l, map->lines[i], &inter)) {
            if (same_point(p, &inter)) {
                Point inter2;
                match = map->lines[i];
                if (is_endpoint(p, match)) {
                    //Trigon t = {pl->location, FR_l->p2, FL_l->p2};
                    // point in FOV if alpha + phi == rho
                    double alpha = interior_angle(FR_l->p2, pl->location,
                            *other_endpoint(p, match));
                    double phi = interior_angle(FL_l->p2, pl->location,
                            *other_endpoint(p, match));
                    double rho = interior_angle(FR_l->p2, pl->location,
                            FL_l->p2);
                    if (intersection(FL_l, map->lines[i], &inter2) ||
                    		fnear(alpha + phi, rho)) break;
                } else {
                    break;
                }
            }
        }
    }

    return match;
}

// True if this point is an endpoint of the line
int is_endpoint(Point *p, Line *l) {
    if (same_point(p, &l->p1) || same_point(p, &l->p2)) return 1;
    else return 0;
}

// Returns opposite end point.  Pre: p is an end point
Point* other_endpoint(Point *p, Line *l) {
    if (same_point(p, &l->p2)) return &l->p1;
    else return &l->p2;
}

/* Returns which of 1 or 2 in p1 and p2 is the left end point of a line from
 the player's perspective. Careful not to mung the point's values...
 This functions acts as though the player's bearing is towards the closest
 point on the line to the player.
 */
Point* left_point(const Player *p, Line *l) {
    Point p1; /* using p's coordinates as the origin */
    Point p2; /* and bearing as x-axis */

    // shift coords
    p1.x = l->p1.x - p->location.x;
    p1.y = l->p1.y - p->location.y;
    p2.x = l->p2.x - p->location.x;
    p2.y = l->p2.y - p->location.y;

    Point A = { 0, 0 }; /* origin, which is player's location       */
    double alpha_1 = interior_angle(A, p1, p2); /* angle at p1                */
    double alpha_2 = interior_angle(A, p2, p1); /* angle at p2                */
    double phi_1 = M_PI_2 - alpha_1; /* abs val offset line perp l */
    double phi_2 = M_PI_2 - alpha_2; /* abs val offset line perp l */
    double rho = 0; /* explanation below          */

    // convert to polar
    r2p(&p1);
    r2p(&p2);

    // Calculate rho, which is the angle of a line perpendicular to l from
    // the player's location and can be used to determine leftedness
    if (same_angle(p1.y - phi_1, p2.y - phi_2) || same_angle(p1.y - phi_1, p2.y
            + phi_2)) rho = p1.y - phi_1;
    else
        if (same_angle(p1.y + phi_1, p2.y - phi_2) || same_angle(p1.y + phi_1,
                p2.y + phi_2)) rho = p1.y + phi_1;

    // Shift angles so that rho is 0 radians
    p1.y -= rho;
    p2.y -= rho;

    // may need to normalize here
    p1.y = normalize_angle(p1.y);
    p2.y = normalize_angle(p2.y);

    // make left of player > 0, right of player < 0
    if (p1.y > M_PI) p1.y -= 2 * M_PI;
    if (p2.y > M_PI) p2.y -= 2 * M_PI;

    if (fnear(p1.y, p2.y)) // neither is leftmost
    return NULL;
    else
        if (p1.y > p2.y) // p1 is lefter
        return &l->p1;
        else return &l->p2; // p2 is lefter
}

/* Returns which of 1 or 2 in p1 and p2 is the right end point of a line from
 the player's perspective. Careful not to mung the point's values...
 */
Point* right_point(const Player *p, Line *l) {
    Point *left = left_point(p, l);
    if (left) return other_endpoint(left, l);
    else return NULL; // in case neither is rightmost
}

// Returns if two points are roughly the same
int same_point(Point *p1, Point *p2) {
    return (fnear(p1->x, p2->x) && fnear(p1->y, p2->y));
}

// Returns if two angles are roughly the same
int same_angle(double a, double b) {
    if (fnear(a, b)) // check the simple case that angles are same
    return 1;
    else { // otherwise check special case where 0 = 2*PI
        a = normalize_angle(a);
        b = normalize_angle(b);
        if (a > M_PI) a -= 2 * M_PI; // angles > PI become negative
        if (b > M_PI) b -= 2 * M_PI;
        return fnear(a, b);
    }
}

// returns 0 <= a < 2*PI
double normalize_angle(double a) {
    while (a >= 2 * M_PI) {
        a -= 2 * M_PI;
    }
    while (a < 0) {
        a += 2 * M_PI;
    }

    return a;
}

// returns angle from origin to point, 0 <= angle < 2*PI
double angle_to_point(Point origin, Point p) {
    p.x -= origin.x;
    p.y -= origin.y;

    double angle = atan(p.y / p.x);
    if (p.x < 0) angle += M_PI;
    return angle;
}

// returns distance from origin of a point
double distance(const Point *p) {
    return sqrt(p->x * p->x + p->y * p->y);
}

/**
 * @param l Line to measure length
 * @return Length of l
 */
double line_length(const Line *l) {
    Point p = {l->p1.x - l->p2.x, l->p1.y - l->p2.y};
    return distance(&p);
}

// changes a point to polar coords. The distance is stored in x and angle in y.
// The angle is between 0 and 2*PI.
Point* r2p(Point *p) {
    double dist = distance(p);
    double angle = atan(p->y / p->x);

    // because atan is -pi/2 to pi/2
    switch (quadrant(p)) {
    case 1:
        break;
    case 2:
    case 3:
        angle = M_PI + angle;
        break;
    case 4:
        angle = 2 * M_PI + angle;
        break;
    }

    // normalize so 0 <= angle < 2*PI
    angle = normalize_angle(angle);

    p->x = dist;
    p->y = angle;

    return p;
}

// changes a point to rectangular coords
Point* p2r(Point *p) {
    double x = p->x * cos(p->y);
    double y = p->x * sin(p->y);
    p->x = x;
    p->y = y;
    return p;
}

// returns quadrant point is in
int quadrant(const Point *p) {
    if (p->y >= 0) {
        if (p->x >= 0) return 1;
        else return 2;
    } else {
        if (p->x >= 0) return 4;
        else return 3;
    }
}

// returns slope of the line, no vertical line test
double slope(const Line *l) {
    return (l->p1.y - l->p2.y) / (l->p1.x - l->p2.x);
}

// returns 1 if line is vertical, else 0.
int is_vertical(const Line *l) {
    if (fnear(l->p1.x, l->p2.x)) return 1;
    else return 0;
}

// interior angle of <BAC in radians
double interior_angle(Point b, Point a, Point c) {
    // shift so a is the origin, making vectors out of b and c
    b.x -= a.x;
    b.y -= a.y;
    c.x -= a.x;
    c.y -= a.y;

    // by using the two definitions of the scalar product
    double angle =
            acos((b.x * c.x + b.y * c.y) / (distance(&b) * distance(&c)));
    return angle;
}

// Returns 1 if a point is within the bounding box defined by the end points of
// a Line, 0 otherwise.
int inside_bb(const Line *l, const Point *p) {
    Point left, right;
    Point top, bottom;

    /* find which point is leftmost and which is rightmost */
    if (l->p1.x < l->p2.x) {
        left = l->p1;
        right = l->p2;
    } else {
        left = l->p2;
        right = l->p1;
    }

    /* same for top and bottom */
    if (l->p1.y > l->p2.y) {
        top = l->p1;
        bottom = l->p2;
    } else {
        top = l->p2;
        bottom = l->p1;
    }

    /* check if point is within the box */
    // extra 1e-9 values added because of floating point errors
    if (is_vertical(l) && fnear(l->p1.x, p->x) && p->y >= bottom.y - 1e-9
            && p->y <= top.y + 1e-9) return 1;
    else
        if (p->x + 1e-9 >= left.x && p->x - 1e-9 <= right.x && p->y + 1e-9
                >= bottom.y && p->y - 1e-9 <= top.y) return 1;
        else return 0;
}

// Returns 1 if a point is inside the triangle, 0 otherwise
int inside_tri(const Trigon *t, const Point *p) {
    double theta_1 = interior_angle(t->p3, *p, t->p2);
    double theta_2 = interior_angle(t->p3, *p, t->p1);
    double theta_3 = interior_angle(t->p1, *p, t->p2);

    double sum = theta_1 + theta_2 + theta_3;

    return (sum >= (2 * M_PI - 0.000001)) ? 1 : 0;
}

// Returns 1 if a point is inside the quadrilateral defined by the end points of
// 2 Lines, 0 otherwise
int inside_quad(const Line *l_1, const Line *l_2, Point *p) {
    Trigon t_1 = {l_1->p1, l_1->p2, l_2->p1};
    Trigon t_2 = {l_2->p1, l_2->p2, l_1->p2};
    return inside_tri(&t_1, p) || inside_tri(&t_2, p);
}
